The present invention relates to reconfigurable devices capable of implementing various functions programmably, and in particular, to programmable interconnect networks as major part of the reconfigurable devices.
Reconfigurable devices such as PLD (Programmable Logic Device), FPGA (Field Programmable Gate Array), etc. which are capable of implementing various functions programmably are progressing remarkably in recent years. Such reconfigurable devices have been used for emulation in the designing of ASICs (Application Specific Integrated Circuits), as replacements for simple peripheral circuits, etc. However, by the technological innovation of these days, the reconfigurable device is now being expected to realize a xe2x80x9creconfigurable computersxe2x80x9d, whose hardware architecture can be reconfigured to be adapted for each application.
In general, the reconfigurable device is composed of a two-dimensional array of function cells (to each of which various logical functions can be set programmably) and a programmable interconnect network which programmably connects the function cells and the other various circuits on the device (for example, I/O circuits, memory, etc.).
For the purpose of efficient interconnection between the function cells and the other various circuits on the device, a variety of programmable interconnect networks having hierarchical structure including lines of various lengths have been devised.
[Prior Art #1]
FIG. 1 is a circuit diagram showing an example of a conventional programmable interconnect network having such a hierarchical structure (hereafter, referred to as xe2x80x9cprior art #1xe2x80x9d) FIG. 1 shows part (a row) of a two-dimensional function cell array and part of the programmable interconnect network corresponding to the row. The programmable interconnect network of the prior art #1 includes a plurality of programmable interconnect ways 20 corresponding to the rows of the two-dimensional function cell array, however, only one programmable interconnect way 20 is shown in FIG. 1. The programmable interconnect way 20 shown in FIG. 1 includes a short programmable interconnect channel 21 which is composed of short lines and a long programmable interconnect channel 22 which is composed of long lines. The short programmable interconnect channel 21 is segmented by programmable switches 58-1 and 58-2 into short sectors 65-1, and the long programmable interconnect channel 22 is segmented by the programmable switches 58-2 into long sectors 65-2.
Each programmable switch (58-1, 58-2) is a circuit for programmably connecting/disconnecting the connection between lines which are connected thereto. Such a programmable switch (58-1, 58-2) is capable of programmably connecting/disconnecting axially aligned and adjacent lines (such as the lines 62-1 and 62-2) or lines running in different channels (such as the lines 61-1 and 62-1).
In such interconnect line structure which is segmented into sectors (short sectors 65-1, long sectors 65-2), a signal to be transferred across multiple sectors has to pass through a lot of programmable switches (58-1, 58-2). Such signal transfer across multiple sectors tends to introduce large delay in comparison with signal transfer in a sector. Further, such signal transfer delay is enhanced if the sizes of macro blocks which are implemented on the chip do not match the sector structure.
Especially when a circuit such as a xe2x80x9cdata pathxe2x80x9d (in which signals are successively transferred across nearby macro blocks and thereby a massive amount of conplicated data processing is performed consequently) is implemented on a sector type interconnect line structure such as the one shown in FIG. 1, some inter-macro-block connections are necessitated to pass through sector boundaries and thereby the aforementioned delay is caused.
Further, when a large-scale circuit is implemented on such a sector type interconnect line structure, a signal has to pass through many sector boundaries whether it is in a macro block or across macro blocks. For such reasons, high performance can not be attained in the sector type interconnect line structure.
Incidentally, the prior art #1 of FIG. 1 is only a simple example for clearly showing the essence of the problems of conventional programmable interconnect networks. Therefore, the number of lines, the sizes of sectors, the number of programmable interconnect channels, etc. shown in FIG. 1 are not essential. A typical programmable interconnect network corresponding to the prior art #1 has been disclosed in U.S. Pat. No. 5,469,003.
[Prior Art #2]
Another sector type interconnect line structure has been disclosed in U.S. Pat. No. 5,218,240 (hereafter, referred to as xe2x80x9cprior art #2xe2x80x9d). In the prior art #2, the short sectors 65-1 and the long sectors 65-2 which have been shown in FIG. 1 are configured as common sectors. However, the function cells 10 in the prior art #2 are not connected to the long programmable interconnect channels 22 (referred to as xe2x80x9cexpress busesxe2x80x9d in the prior art #2) and are connected to the short programmable interconnect channels 21 (referred to as xe2x80x9clocal busesxe2x80x9d in the prior art #2) only.
Therefore, the long programmable interconnect channel 22 in the prior art #2 is designed to make access to a function cell 10 through a programmable switch 58-2 and a short programmable interconnect channel 21. By such composition, the load capacitance of the long programmable interconnect channel 22 is reduced and thereby high-speed signal transfer is realized.
However, in the interconnect line structure of the prior art #2, the interconnect network is totally segmented into sectors, without additional long interconnect line resources. Therefore, the demerits of the sector segmentation can not be compensated for at all, differently from the prior art #1 of FIG. 1 in which the demerits could be partially compensated for by use of the long sector 65-2 which bypasses the boundaries of short sectors 65-1.
[Prior Art #3]
Next, problems concerning the connection between the programmable interconnect network and the function cells 10 will be explained. FIG. 2 is a circuit diagram showing a conventional connection method (hereafter, referred to as xe2x80x9cprior art #3xe2x80x9d) for connecting a hierarchical programmable interconnect network (not limited to sector type network) and function cells 10. Such a connection method has been disclosed in ATandT Field-Programmable Gate Arrays Data Book (April 1995). The programmable interconnect network of the prior art #3 includes a plurality of horizontal programmable interconnect ways 20 which extend in the horizontal direction and a plurality of vertical programmable interconnect ways 30 which extend in the vertical direction. Incidentally, a horizontal programmable interconnect way 20 and a vertical programmable interconnect way 30 corresponding to a function cell 10 are shown in FIG. 2 for the sake of simplicity.
The horizontal programmable interconnect way 20 show in FIG. 2 at least includes a short horizontal programmable interconnect channel 21 and a long horizontal programmable interconnect channel 22, and the vertical programmable interconnect way 30 at least includes a short vertical programmable interconnect channel 31 and a long vertical programmable interconnect channel 32.
At the intersection 59 of the horizontal programmable interconnect way 20 and the vertical programmable interconnect way 30, an intersection programmable switch 55 is provided so as to programmably connect/disconnect the connections between the intersecting lines.
The function cell 10 shown in FIG. 2 includes an input selection switch 11, a function block 13 and an output selection switch 15. The function block 13 is provided with two or more functions and a function is programmably selected from the functions and set to the function block 13. The input selection switch 11 selects one or more signals from signals supplied from lines of the programmable interconnect network and supplies the selected signals to the function block 13 as input signals 12. The function block 13 generates an output signal 14 from the input signals 12 according to the function which has been set thereto and outputs the output signal 14 to the output selection switch 15. The output selection switch 15 outputs the output signal 14 to zero or more of the lines of the programmable interconnect network selectively.
In the prior art #3, a function cell 10 is directly connected to all the lines of the horizontal programmable interconnect way 20 and the vertical programmable interconnect way 30 associated with the function cell 10. Such structure seems to be capable of transferring signals faster than other structure employing indirect connections by use of other lines.
However, in such structure employing direct connection, each line has connections with all the function cells 10 through which the line passes, thereby large load capacitance is added to the line. Especially in long lines, the load capacitance becomes very large and thereby signal transfer is delayed much.
Further, if a large number of interconnect line resources are prepared in the programmable interconnect network for securing routability, the sizes of an input selection switch 11 (for selecting an input signal from signals supplied from the large number of lines) and an output selection switch 15 (for selecting output signals to be outputted to the large number of lines) of the function cell 10 (see FIG. 2) are necessitated to be very large and thereby serious penalty is caused both in size (area of circuit) and delay.
While the intersection programmable switches 55 in the prior art #3 of FIG. 2 are provided to limited intersection points in the intersection 59 of the horizontal programmable interconnect way 20 and the vertical programmable interconnect way 30, actually, the programmable switches 55 are generally provided to more intersection points and programmable switches between parallel lines might be provided in order to improve the routability. Therefore, many factors exists behind the increase of size (area of circuit) and delay.
On the other hand, if the number of lines connected to the function cell 10 is decreased in order to reduce the load capacitance of lines of the programmable interconnect network as a factor of increase of size and delay, accessibility of the function cell 10 to all the lines (or most lines) of the programmable interconnect network is lost.
The above direct connection method which directly connects every two points (between which connection is necessary) by use of switches involves serious problems as explained above. Incidentally, while the input selection switch 11 and the output selection switch 15 in FIG. 2 are drawn in the function cell 10 for the sake of simplicity, the essence of the above problems does not change even if the input selection switch 11 and/or the output selection switch 15 are provided outside the function cell 10 (in the areas 19 shown in FIG. 2, for example). Incidentally, the composition shown in FIG. 2 is only an example for clearly showing the essence of the above problems, therefore, the number of lines, switches, programmable interconnect channels, etc. shown in FIG. 2 are of course not essential. Further, while the horizontal programmable interconnect way 20 and the vertical programmable interconnect way 30 which are connected to the function cell 10 were placed above the function cell 10 and on the left-hand side of the function cell 10 in FIG. 2 respectively, the essence of the above problems does not change even if horizontal programmable interconnect ways 20 are provided above and below the function cell 10 and vertical programmable interconnect ways 30 are provided on both sides of the function cell 10 so as to be connected thereto as disclosed in ATandT Field-Programmable Gate Arrays Data Book (April 1995).
[Prior Art #4]
In order to resolve the above problems related to the sector segmentation and the direct connection method, an interconnect line structure shown in FIG. 3 has been proposed in U.S. Pat. No. 5,631,578 (hereafter, referred to as xe2x80x9cprior art #4xe2x80x9d). In the structure of FIG. 3, the sector type interconnect line structure of the Prior Art #2 (U.S. Pat. No. 5,218,240) has been improved.
The interconnect line structure shown in FIG. 3 includes a pair of programmable interconnect ways 20-1 and 20-2 which run in parallel. The first programmable interconnect way 20-1 includes a first local bus 23-1, a first express bus 24-1 and a first super bus 25-1. The second programmable interconnect way 20-2 includes a second local bus 23-2, a second express bus 24-2 and a second super bus 25-2.
Lines in the local bus (23-1, 23-2) are connected in series by first programmable switches 58-1 and second programmable switches 58-2, and each of the lines is also directly connected to a function cell 10.
Lines in the express bus (24-1, 24-2) are connected in series by first programmable switches 58-1, and each of the lines is also connected to a corresponding local bus (23-1, 23-2) by a first programmable switch 58-1.
The super bus (25-1, 25-2) is connected to lines of a corresponding local bus (23-1, 23-2) by second programmable switches 58-2, however, the super bus (25-1, 25-2) is not segmented by the second programmable switches 58-2. The express buses 24-1 and 24-2 and the super buses 25-1 and 25-2 are not directly connected to function cells 10.
The first programmable switches 58-1 and the second programmable switches 58-2 are placed alternately for segmenting and connecting the local bus (23-1, 23-2), in which horizontal positions of the two types of programmable switches 58-1 and 58-2 are switched between the first programmable interconnect way 20-1 and the second programmable interconnect way 20-2.
In such composition, the first express bus 24-1 and the second express bus 24-2 are placed so as to have their first programmable switches 58-1 at different horizontal positions, thereby a seamless line of an express bus (24-1, 24-2) is secured at any horizontal position.
Further, the express buses 24-1 and 24-2 and the super buses 25-1 and 25-2 do not have direct connections with the function cells 10, thereby load capacitance of the buses can be reduced and thereby high-speed signal transfer is made possible.
Each express/super bus (24-1, 24-2, 25-1, 25-2) is designed to make access to the function cells 10 through a programmable switch (58-1, 58-2) which is connected thereto and a local bus (23-1, 23-2).
The above technology of the prior art #4 partially relieves the problems of the sector segmentation (sector type interconnect line structure), however, the problems are not essentially resolved since the local buses 23-1 and 23-2 are still totally segmented into sectors. Usage frequency of short lines is generally higher than that of long lines, therefore, the problems related to the sector segmentation also occurs more frequently in short lines.
Especially when the aforementioned data path etc. (in which signals are successively transferred across nearby macro blocks and thereby a massive amount of complicated data processing is conducted) is implemented on such a sector type interconnect line structure, the problems of the sector segmentation occur frequently.
Therefore, the interconnect line structure of FIG. 3 is insufficient for resolving the problems caused by the sector segmentation. Incidentally, while other interconnect line resources are also shown in U.S. Pat. No. 5,631,578, essential part necessary for the explanation of the essence of problems has been shown here.
Further, in the prior art #4, interconnect line structure in the horizontal direction and that in the vertical direction are designed in the same way. Such an isotropic interconnect line structure seems to be advantageous from the viewpoint of the implementation of various circuits (which is the purpose of the reconfigurable device).
However, in a large-scale application circuit, most part of the circuit is usually occupied by data paths for successively processing multiple-bit data. Such a tendency is prominent in the field of reconfigurable computers which are expected to create a big market.
In such a multiple-bit data path, demand for signal transfer in the bit string direction or bit direction (i.e. the vertical direction in which the carry signal is transferred) is much lower than that in the data direction (horizontal direction), therefore, the aforementioned isotropic interconnect line structure causes a lot of waste when such multiple-bit data paths are implemented on the reconfigurable device.
[Prior Art #5]
Meanwhile, another interconnect line structure has been disclosed in U.S. Pat. No. 5,592,106 (hereafter, referred to as xe2x80x9cprior art #5xe2x80x9d) in order to cope with the problems related to the sector segmentation and the direct connection method. FIG. 4 is a circuit diagram showing the interconnect line structure of the prior art #5.
In the interconnect line structure of FIG. 4, a horizontal programmable interconnect way 20 includes a local feedback channel 26, an intermediate channel 27, a half-length channel 28 and a global channel 29. The local feedback channel 26 and the intermediate channel 27 are provided to the horizontal programmable interconnect way 20 as a short-range network, and the global channel 29 and the half-length channel 28 are provided as a long-range network.
The global channel 29 is composed of lines whose lengths are the same as the total width of the two-dimensional function cell array, and the half-length channel 28 is composed of lines of half the length. The length of each line of the intermediate channel 27 is almost the same as that of the local feedback channel 26. Each long-range input selection switch 11-2 selects a signal from signals supplied from the long-range network (global channel 29, half-length channel 28) and supplies the selected signal to a corresponding line of the intermediate channel 27. Meanwhile, each short-range input selection switch 11-1 selects a signal from signals supplied from the short-range network (intermediate channel 27, local feedback channel 26) and supplies the selected signal to the input terminal 12 of the function block 13 of a corresponding function cell 10.
The output terminal 14 of the function block 13 of each function cell 10 is connected to a corresponding line of the local feedback channel 26 directly (through no programmable switch). The output terminal 14 is also selectively connected to the long-range network through an output selection switch 15.
The short-range input selection switch 11-1 and the long-range input selection switch 11-2 do not segment (disconnect) lines which are connected thereto.
In this prior art, there is no programmable switch between axially aligned and adjacent lines. Therefore, those lines are not connectable to one another.
The interconnect line structure of the prior art #5 has characteristic xe2x80x9cshift structurexe2x80x9d. The horizontal positions of the lines of the intermediate channel 27 and the local feedback channel 26 are successively shifted with a shift width that is the same as the interval between function cells 10. In the short-range network having such shift structure, one or more seamless lines are secured at any horizontal position (even at a horizontal position where a line gap exists), therefore, the short-range network is not totally segmented into sectors. Further, the long-range network, which is not connected to the input terminals 12 of the function blocks 13 of the function cells 10 directly, is connected to the input terminals 12 through the intermediate channel 27.
In such structure, enough accessibility of the long-range network to the function cell 10 can be attained by only slight connection of each long-range input selection switch 11-2 to small part of the long-range network. Therefore, load capacitance of the long-range input selection switches 11-2 that is added to each line of the long-range network can be reduced by such structure.
However, in the interconnect line structure of the prior art #5, the half-length channel 28 is still totally segmented into sectors. Further, output terminals of the function cells 10 are connected to the long-range network directly (not through other channels). In such composition, the number of function cells 10 that are connected to a line of the long-range network has to be reduced to small in order to avoid the increase of the load capacitance due to the output of the function cells 10. Therefore, when the number of function cells 10 is set larger, the number of lines of the long-range network (long lines) is necessitated to be increased much.
However, usage frequency of long lines are generally lower than that of short lines, and thus the above structure involves a lot of waste. On the other hand, if the number of long lines of the long-range network is reduced, the number of function cells 10 connected to each long line increases, thereby the load capacitance increases and thereby long delay is caused.
Further, although not shown in FIG. 4, the prior art #5 employs anisotropic interconnect line structure in which interconnect line structure in the horizontal direction is different from that in the vertical direction. Concretely, only a global channel 29 is provided to the vertical programmable interconnect way 30, and the output terminals of the function cells 10 are directly connected to the global channel 29. However, in such composition, load capacitance on each line of the global channel 29 is necessitated to be large and thereby signal transfer speed is necessitated to be lowered.
Further, in the prior art #5, each line of the local feedback channel 26 is directly connected to the output terminal of only one function cell 10, therefore, a larger number of lines becomes necessary in the local feedback channel 26 in comparison with cases where a line of the local feedback channel 26 is shared by two or more function cells 10. The increase of the number of lines of the local feedback channel 26 causes not only an increase of circuit area of the local feedback channel 26 but also an increase of chip sizes (circuit scales) of the short-range input selection switches 11-1.
Incidentally, the structure which has been shown in FIG. 4 is only an example for clearly showing the essence of the problems, and thus interconnect line structures disclosed in the prior art #5 (U.S. Pat. No. 5,592,106) are of course not limited to the structure FIG. 4. The number of lines, switches, line lengths, etc. which have been shown in FIG. 4 as an example are of course not essential.
As described above, the conventional programmable interconnect networks of reconfigurable devices involve the following problems or drawbacks.
First, large-scale application circuits can not display their original high performance when implemented on conventional reconfigurable devices (programmable interconnect networks) having the sector type interconnect line structure. Due to the sector type interconnect line structure, restriction arises on the sizes of macro blocks of the large-scale application circuit, thereby the derivation of high performance from the large-scale application circuit becomes difficult. Further, in inter-macro-block signal transfer, signals have to pass through a large number of sector boundaries and thereby signal delay is necessitated to be large.
Second, the area on the chip that is occupied by switches (programmable switches, intersection programmable switches, input/output selection switches, etc.) is necessitated to be large. Direct connections by use of such switches are provided between the programmable interconnect network and the function cells 10 and between parts of the programmable interconnect network requiring connections, thereby a large number of switches are required and thereby circuit area occupied by the switches becomes large. Further, large load capacitance due to the many switches is added to each line, thereby long delay is caused in inter-macro-block signal transfer.
Third, conventional programmable interconnect networks tend to involve a lot of waste when a multiple-bit data processing circuit is implemented thereon, since isotropic interconnect line structure is necessitated to include a large number of unnecessary interconnect line resources in a direction of lower demand (bit direction).
Fourth, the number of necessary lines tends to increase as the line length becomes longer, since the outputs of the function cells 10 are directly supplied to long lines. Usage frequency of long lines is generally lower than that of short lines, therefore such composition involves a lot of waste.
It is therefore the primary object of the present invention to provide a reconfigurable device having a programmable interconnect network, in which enough routability is secured by use of small numbers of switches and lines.
Another object of the present invention is to provide a reconfigurable device having a programmable interconnect network, by which multiple-bit data paths can be implemented efficiently.
Another object of the present invention is to provide a reconfigurable device having a programmable interconnect network which is suitable for the implementation of high-speed data paths.
In accordance with a first aspect of the present invention, there is provided a reconfigurable device which is constructed as an integrated circuit including a plurality of function cells and a programmable interconnect network which programmably connects the function cells. The integrated circuit is constructed as a two-dimensional array of tiles which extends in a horizontal direction and a vertical direction. Each tile includes one of the function cells and part of the programmable interconnect network in the vicinity of the function cell. Each function cell includes: a function block having first input terminals, one or more first output terminals, and functions from which a function is programmably selected and set thereto, for generating an output signal from signals supplied to the first input terminals according to the function which has been set thereto and outputting the generated output signal from the one or more first output terminals; input selection switches each of which has second input terminals and a second output terminal, for programmably setting one of the second input terminals to be connected to the second output terminal; an output selection switch having a third input terminal and third output terminals, for programmably setting each of the third output terminals to be connected to the third input terminal or to be in high impedance status; and input/output lines which are connected to the second input terminals of the input selection switches and the third output terminals of the output selection switch. Each first input terminal of the function block is connected to the second output terminal of corresponding one of the input selection switches, and the third input terminal of the output selection switch is connected to the first output terminal of the function block. The programmable interconnect network includes horizontal programmable interconnect ways each of which runs in the horizontal direction in each row of the two-dimensional array respectively. The horizontal programmable interconnect way includes a short horizontal programmable interconnect channel and a long horizontal programmable interconnect channel. The short horizontal programmable interconnect channel includes M short horizontal lanes (M: natural number) each of which includes short horizontal programmable switches which are provided to every M tiles aligned in the horizontal direction and short horizontal interconnect line segments as seamless lines connecting adjacent short horizontal programmable switches. The horizontal positions of tiles containing the short horizontal programmable switches of each short horizontal lane of the short horizontal programmable interconnect channel are successively shifted between adjacent short horizontal lanes by 1 tile width. The long horizontal programmable interconnect channel includes M long horizontal lanes each of which includes long horizontal programmable switches which are provided to every N tiles (N: natural number) aligned in the horizontal direction and long horizontal interconnect line segments as seamless lines connecting adjacent long horizontal programmable switches. The horizontal positions of tiles containing the long horizontal programmable switches of each long horizontal lane of the long horizontal programmable interconnect channel are successively shifted between adjacent long horizontal lanes by P tile widths (P: natural numberxe2x89xa74, P=N/M). Each short horizontal interconnect line segment is connected to one of the long horizontal interconnect line segments through an inter-horizontal-channel programmable switch which is provided to each tile. Long horizontal interconnect line segments to which the inter-horizontal-channel programmable switches of arbitrary M contiguous tiles aligned in the horizontal direction are connected belong to different long horizontal lanes. Each input/output line of the function cell is directly connected to corresponding one of the short horizontal interconnect line segments running in the tile containing the function cell. Each of the programmable switches programmably connects/disconnects the connection between the line segments that are connected thereto.
In accordance with a second aspect of the present invention, in the first aspect, each column of the two-dimensional array is divided into ALUs (Arithmetic and Logic Units) each of which is composed of U contiguous tiles (U: natural number) of the column. The function cells contained in the ALU at least share an input signal that is inputted to an input selection switch or configuration data designating the functions of the function block and the input selection switch. The programmable interconnect network further includes vertical programmable interconnect ways each of which runs in the vertical direction in each column of the two-dimensional array respectively. The vertical programmable interconnect way includes a short vertical programmable interconnect channel and a long vertical programmable interconnect channel. The short vertical programmable interconnect channel includes W short vertical lanes (W: natural number less than M) each of which includes short vertical programmable switches which are provided to every V tiles (V: integral multiple of U) aligned in the vertical direction and short vertical interconnect line segments as seamless lines connecting adjacent short vertical programmable switches. At least one of the W short horizontal lanes of the short vertical programmable interconnect channel is composed of short vertical interconnect line segments each of which seamlessly stretches from the uppermost tile to the lowermost tile of an ALU. The long vertical programmable interconnect channel includes L long vertical lanes (L: natural number xe2x89xa6W) each of which is composed of long vertical interconnect line segments whose lengths are at least 4 times as long as the short vertical interconnect line segment. Each short vertical interconnect line segment is connected to one of the long vertical interconnect line segment through an inter-vertical-channel programmable switch. Each short vertical interconnect line segment is connected to one of the short horizontal interconnect line segments intersecting the short vertical interconnect line segment in each row of the two-dimensional array through an intersection programmable switch.
In accordance with a third aspect of the present invention, in the first aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a fourth aspect of the present invention, in the second aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a fifth aspect of the present invention, there is provided a reconfigurable device which is constructed as an integrated circuit including a plurality of function cells and a programmable interconnect network which programmably connects the function cells. The integrated circuit is constructed as a two-dimensional array of tiles which extends in a horizontal direction and a vertical direction. Each tile includes one of the function cells and part of the programmable interconnect network in the vicinity of the function cell. Each function cell includes: a function block having first input terminals, one or more first output terminals, and functions from which a function is programmably selected and set thereto, for generating an output signal from signals supplied to the first input terminals according to the function which has been set thereto and outputting the generated output signal from the one or more first output terminals; input selection switches each of which has second input terminals and a second output terminal, for programmably setting one of the second input terminals to be connected to the second output terminal; an output selection switch having a third input terminal and third output terminals, for programmably setting each of the third output terminals to be connected to the third input terminal or to be in high impedance status; and input/output lines which are connected to the second input terminals of the input selection switches and the third output terminals of the output selection switch. Each first input terminal of the function block is connected to the second output terminal of corresponding one of the input selection switches, and the third input terminal of the output selection switch is connected to the first output terminal of the function block. The programmable interconnect network has two or more parallelly running horizontal programmable interconnect ways in each row of the two-dimensional array. Each of the horizontal programmable interconnect ways includes a short horizontal programmable interconnect channel and a long horizontal programmable interconnect channel. The short horizontal programmable interconnect channel includes M short horizontal lanes (M: natural number) each of which includes short horizontal programmable switches which are provided to every M tiles aligned in the horizontal direction and short horizontal interconnect line segments as seamless lines connecting adjacent short horizontal programmable switches. The horizontal positions of tiles containing the short horizontal programmable switches of each short horizontal lane of the short horizontal programmable interconnect channel are successively shifted between adjacent short horizontal lanes by 1 tile width. The long horizontal programmable interconnect channel includes M long horizontal lanes each of which includes long horizontal programmable switches which are provided to every N tiles (N: natural number) aligned in the horizontal direction and long horizontal interconnect line segments as seamless lines connecting adjacent long horizontal programmable switches. The horizontal positions of tiles containing the long horizontal programmable switches of each long horizontal lane of the long horizontal programmable interconnect channel are successively shifted between adjacent long horizontal lanes by P tile widths (P: natural numberxe2x89xa74, P=N/M). In each horizontal programmable interconnect way, each short horizontal interconnect line segment is connected to one of the long horizontal interconnect line segments of the horizontal programmable interconnect way through an inter-horizontal-channel programmable switch which is provided to each tile, and long horizontal interconnect line segments to which the inter-horizontal-channel programmable switches of arbitrary M contiguous tiles aligned in the horizontal direction are connected belong to different long horizontal lanes. Each input/output line of the function cell is directly connected to corresponding one of the short horizontal interconnect line segments running in the tile containing the function cell. Each of the programmable switches programmably connects/disconnects the connection between the line segments that are connected thereto.
In accordance with a sixth aspect of the present invention, in the fifth aspect, each column of the two-dimensional array is divided into ALUs (Arithmetic and Logic Units) each of which is composed of U contiguous tiles (U: natural number) of the column. The function cells contained in the ALU at least share an input signal that is inputted to an input selection switch or configuration data designating the functions of the function block and the input selection switch. The programmable interconnect network further includes vertical programmable interconnect ways each of which runs in the vertical direction in each column of the two-dimensional array respectively. The vertical programmable interconnect way includes a short vertical programmable interconnect channel and a long vertical programmable interconnect channel. The short vertical programmable interconnect channel includes W short vertical lanes (W: natural number less than M) each of which includes short vertical programmable switches which are provided to every V tiles (V: integral multiple of U) aligned in the vertical direction and short vertical interconnect line segments as seamless lines connecting adjacent short vertical programmable switches. At least one of the W short horizontal lanes of the short vertical programmable interconnect channel is composed of short vertical interconnect line segments each of which seamlessly stretches from the uppermost tile to the lowermost tile of an ALU. The long vertical programmable interconnect channel includes L long vertical lanes (L: natural number xe2x89xa6W) each of which is composed of long vertical interconnect line segments whose lengths are at least 4 times as long as the short vertical interconnect line segment. Each short vertical interconnect line segment is connected to one of the long vertical interconnect line segment through an inter-vertical-channel programmable switch. Each short vertical interconnect line segment is connected to one of the short horizontal interconnect line segments intersecting the short vertical interconnect line segment in each row of the two-dimensional array through an intersection programmable switch. Intersection programmable switches that are contained in the same tile is connected to different short horizontal interconnect line segments.
In accordance with a seventh aspect of the present invention, in the fifth aspect, the natural numbers M and P are set to be relatively prime.
In accordance with an eighth aspect of the present invention, in the sixth aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a ninth aspect of the present invention, in the fifth aspect, the horizontal positions of the long horizontal programmable switches in each horizontal programmable interconnect way are shifted between at least two of the two or more horizontal programmable interconnect ways parallelly running in each row of the two-dimensional array by a tile width or more.
In accordance with a tenth aspect of the present invention, in the sixth aspect, the horizontal positions of the long horizontal programmable switches in each horizontal programmable interconnect Away are shifted between at least two of the two or more horizontal programmable interconnect ways parallelly running in each row of the two-dimensional array by a tile width or more.
In accordance with an eleventh aspect of the present invention, in the ninth aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a twelfth aspect of the present invention, in the tenth aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a thirteenth aspect of the present invention, in the fifth aspect, the horizontal positions of the long horizontal programmable switches in each horizontal programmable interconnect way are successively shifted between adjacent ones of the two or more horizontal programmable interconnect ways parallelly running in each row of the two-dimensional array by a tile width or more.
In accordance with a fourteenth aspect of the present invention, in the sixth aspect, the horizontal positions of the long horizontal programmable switches in each horizontal programmable interconnect way are successively shifted between adjacent ones of the two or more horizontal programmable interconnect ways parallelly running in each row of the two-dimensional array by a tile width or more.
In accordance with a fifteenth aspect of the present invention, in the thirteenth aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a sixteenth aspect of the present invention, in the fourteenth aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a seventeenth aspect of the present invention, there is provided a reconfigurable device which is constructed as an integrated circuit including a plurality of function cells and a programmable interconnect network which programmably connects the function cells. The integrated circuit is constructed as a two-dimensional array of tiles which extends in a horizontal direction and a vertical direction. Each tile includes one of the function cells and part of the programmable interconnect network in the vicinity of the function cell. Each function cell includes: a function block having first input terminals, one or more first output terminals, and functions from which a function is programmably selected and set thereto, for generating an output signal from signals supplied to the first input terminals according to the function which has been set thereto and outputting the generated output signal from the one or more first output terminals; input selection switches each of which has second input terminals and a second output terminal, for programmably setting one of the second input terminals to be connected to the second output terminal; an output selection switch having a third input terminal and third output terminals, for programmably setting each of the third output terminals to be connected to the third input terminal or to be in high impedance status; and input/output lines which are connected to the second input terminals of the input selection switches and the third output terminals of the output selection switch. Each first input terminal of the function block is connected to the second output terminal of corresponding one of the input selection switches, and the third input terminal of the output selection switch is connected to the first output terminal of the function block. The programmable interconnect network has two or more parallelly running horizontal programmable interconnect ways in each row of the two-dimensional array. Each of the horizontal programmable interconnect ways includes a short horizontal programmable interconnect channel, and each of part of the horizontal programmable interconnect ways further includes a long horizontal programmable interconnect channel. The short horizontal programmable interconnect channel includes M short horizontal lanes (M: natural number) each of which includes short horizontal programmable switches which are provided to every M tiles aligned in the horizontal direction and short horizontal interconnect line segments as seamless lines connecting adjacent short horizontal programmable switches. The horizontal positions of tiles containing the short horizontal programmable switches of each short horizontal lane of the short horizontal programmable interconnect channel are successively shifted between adjacent short horizontal lanes by 1 tile width. The long horizontal programmable interconnect channel includes M long horizontal lanes each of which includes long horizontal programmable switches which are provided to every N tiles (N: natural number) aligned in the horizontal direction and long horizontal interconnect line segments as seamless lines connecting adjacent long horizontal programmable switches. The horizontal positions of tiles containing the long horizontal programmable switches of each long horizontal lane of the long horizontal programmable interconnect channel are successively shifted between adjacent long horizontal lanes by P tile widths (P: natural numberxe2x89xa74, P=N/M). In each horizontal programmable interconnect way that includes a long horizontal programmable interconnect channel, each short horizontal interconnect line segment is connected to one of the long horizontal interconnect line segments of the horizontal programmable interconnect way through an inter-horizontal-channel programmable switch which is provided to each tile, and long horizontal interconnect line segments to which the inter-horizontal-channel programmable switches of arbitrary M contiguous tiles aligned in the horizontal direction are connected belong to different long horizontal lanes. Each input/output line of the function cell is directly connected to corresponding one of the short horizontal interconnect line segments running in the tile containing the function cell. Each of the programmable switches programmably connects/disconnects the connection between the line segments that are connected thereto.
In accordance with an eighteenth aspect of the present invention, in the seventeenth aspect, each column of the two-dimensional array is divided into ALUs (Arithmetic and Logic Units) each of which is composed of U contiguous tiles (U: natural number) of the column. The function cells contained in the ALU at least share an input signal that is inputted to an input selection switch or configuration data designating the functions of the function block and the input selection switch. The programmable interconnect network further includes vertical programmable interconnect ways each of which runs in the vertical direction in each column of the two-dimensional array respectively. The vertical programmable interconnect way includes a short vertical programmable interconnect channel and a long vertical programmable interconnect channel. The short vertical programmable interconnect channel includes W short vertical lanes (W: natural number less than M) each of which includes short vertical programmable switches which are provided to every V tiles (V: integral multiple of U) aligned in the vertical direction and short vertical interconnect line segments as seamless lines connecting adjacent short vertical programmable switches. At least one of the W short horizontal lanes of the short vertical programmable interconnect channel is composed of short vertical interconnect line segments each of which seamlessly stretches from the uppermost tile to the lowermost tile of an ALU. The long vertical programmable interconnect channel includes L long vertical lanes (L: natural numberxe2x89xa6W) each of which is composed of long vertical interconnect line segments whose lengths are at least 4 times as long as the short vertical interconnect line segment. Each short vertical interconnect line segment is connected to one of the long vertical interconnect line segment through an inter-vertical-channel programmable switch. Each short vertical interconnect line segment is connected to one of the short horizontal interconnect line segments intersecting the short vertical interconnect line segment in each row of the two-dimensional array through an intersection programmable switch. Intersection programmable switches that are contained in the same tile is connected to different short horizontal interconnect line segments.
In accordance with a nineteenth aspect of the present invention, in the seventeenth aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a twentieth aspect of the present invention, in the eighteenth aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a twenty-first aspect of the present invention, in the seventeenth aspect, in at least one horizontal programmable interconnect way that includes no long horizontal programmable interconnect channel, each short horizontal interconnect line segment is connected to a long horizontal interconnect line segment of a horizontal programmable interconnect way that includes a long horizontal programmable interconnect channel through an inter-horizontal-channel programmable switch which is provided to each tile, and long horizontal interconnect line segments to which the inter-horizontal-channel programmable switches of arbitrary M contiguous tiles aligned in the horizontal direction are connected belong to different long horizontal lanes.
In accordance with a twenty-second aspect of the present invention, in the eighteenth aspect, in at least one horizontal programmable interconnect way that includes no long horizontal programmable interconnect channel, each short horizontal interconnect line segment is connected to a long horizontal interconnect line segment of a horizontal programmable interconnect way that includes a long horizontal programmable interconnect channel through an inter-horizontal-channel programmable switch which is provided to each tile, and long horizontal interconnect line segments to which the inter-horizontal-channel programmable switches of arbitrary M contiguous tiles aligned in the horizontal direction are connected belong to different long horizontal lanes.
In accordance with a twenty-third aspect of the present invention, in the twenty-first aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a twenty-fourth aspect of the present invention, in the twenty-second aspect, the natural numbers M and P are set to be relatively prime.
In accordance with a twenty-fifth aspect of the present invention, there is provided a reconfigurable device which is constructed as an integrated circuit including a plurality of function cells and a programmable interconnect network which programmably connects the function cells. The integrated circuit is constructed as a two-dimensional array of tiles which extends in a horizontal direction and a vertical direction. Each tile includes one of the function cells and part of the programmable interconnect network in the vicinity of the function cell. Each function cell includes: a function block having first input terminals, one or more first output terminals, and functions from which a function is programmably selected and set thereto, for generating an output signal from signals supplied to the first input terminals according to the function which has been set thereto and outputting the generated output signal from the one or more first output terminals; input selection switches each of which has second input terminals and a second output terminal, for programmably setting one of the second input terminals to be connected to the second output terminal; an output selection switch having a third input terminal and third output terminals, for programmably setting each of the third output terminals to be connected to the third input terminal or to be in high impedance status; and input/output lines which are connected to the second input terminals of the input selection switches and the third output terminals of the output selection switch. Each first input terminal of the function block is connected to the second output terminal of corresponding one of the input selection switches, and the third input terminal of the output selection switch is connected to the first output terminal of the function block. The programmable interconnect network has J parallelly running horizontal programmable interconnect ways (J: natural number) in each row of the two-dimensional array. Each of the J horizontal programmable interconnect ways includes a short horizontal programmable interconnect channel. Each of K horizontal programmable interconnect ways (K: natural numberxe2x89xa6J) selected out of the J horizontal programmable interconnect ways further includes a long horizontal programmable interconnect channel. In each j-th horizontal programmable interconnect way (j: natural numberxe2x89xa6J) included in the J horizontal programmable interconnect ways, the short horizontal programmable interconnect channel includes Mj short horizontal lanes (Mj: natural number) each of which includes short horizontal programmable switches which are provided to every Mj tiles aligned in the horizontal direction and short horizontal interconnect line segments as seamless lines connecting adjacent short horizontal programmable switches, and the horizontal positions of tiles containing the short horizontal programmable switches of each short horizontal lane are successively shifted between adjacent short horizontal lanes by 1 tile width. In each k-th horizontal programmable interconnect way (k: natural numberxe2x89xa6K) included in the K horizontal programmable interconnect ways, the long horizontal programmable interconnect channel includes Mk long horizontal lanes (Mk: natural number) each of which includes long horizontal programmable switches which are provided to every Nk tiles (Nk: natural number) aligned in the horizontal direction and long horizontal interconnect line segments as seamless lines connecting adjacent long horizontal programmable switches, and the horizontal positions of tiles containing the long horizontal programmable switches of each long horizontal lane of the long horizontal programmable interconnect channel are successively shifted between adjacent long horizontal lanes by Pk tile widths (Pk: natural numberxe2x89xa74, Pk=Nk/Mk). At least two selected from the natural numbers Pk (kxe2x89xa6K) are set to be different from each other, or at least two selected from the natural numbers Mk (kxe2x89xa6K) are set to be different from each other. In each k-th horizontal programmable interconnect way (kxe2x89xa6K) included in the K horizontal programmable interconnect ways, each short horizontal interconnect line segment is connected to one of the long horizontal interconnect line segments of the k-th horizontal programmable interconnect way through an inter-horizontal-channel programmable switch which is provided to each tile, and long horizontal interconnect line segments to which the inter-horizontal-channel programmable switches of arbitrary Mk contiguous tiles aligned in the horizontal direction are connected belong to different long horizontal lanes. Each input/output line of the function cell is directly connected to corresponding one of the short horizontal interconnect line segments running in the tile containing the function cell. Each of the programmable switches programmably connects/disconnects the connection between the line segments that are connected thereto.
In accordance with a twenty-sixth aspect of the present invention, in the twenty-fifth aspect, each column of the two-dimensional array is divided into ALUs (Arithmetic and Logic Units) each of which is composed of U contiguous tiles (U: natural number) of the column. The function cells contained in the ALU at least share an input signal that is inputted to an input selection switch or configuration data designating the functions of the function block and the input selection switch. The programmable interconnect network further includes vertical programmable interconnect ways each of which runs in the vertical direction in each column of the two-dimensional array respectively. The vertical programmable interconnect way includes a short vertical programmable interconnect channel and a long vertical programmable interconnect channel. The short vertical programmable interconnect channel includes W short vertical lanes (W: natural number less than Min (Mk)) each of which includes short vertical programmable switches which are provided to every V tiles (V: integral multiple of U) aligned in the vertical direction and short vertical interconnect line segments as seamless lines connecting adjacent short vertical programmable switches. At least one of the W short horizontal lanes of the short vertical programmable interconnect channel is composed of short vertical interconnect line segments each of which seamlessly stretches from the uppermost tile to the lowermost tile of an ALU. The long vertical programmable interconnect channel includes L long vertical lanes (L: natural numberxe2x89xa6W) each of which is composed of long vertical interconnect line segments whose lengths are at least 4 times as long as the short vertical interconnect line segment. Each short vertical interconnect line segment is connected to one of the long vertical interconnect line segments through an inter-vertical-channel programmable switch. Each short vertical interconnect line segment is connected to one of the short horizontal interconnect line segments intersecting the short vertical interconnect line segment in each row of the two-dimensional array through an intersection programmable switch. Intersection programmable switches that are contained in the same tile is connected to different short horizontal interconnect line segments.
In accordance with a twenty-seventh aspect of the present invention, in the twenty-fifth aspect, the natural numbers Mk and Pk are set to be relatively prime in at least one horizontal programmable interconnect way included in the K horizontal programmable interconnect ways.
In accordance with a twenty-eighth aspect of the present invention, in the twenty-sixth aspect, the natural numbers Mk and Pk are set to be relatively prime in at least one horizontal programmable interconnect way included in the K horizontal programmable interconnect ways.
In accordance with a twenty-ninth aspect of the present invention, in the twenty-fifth aspect, in at least one horizontal programmable interconnect way that is not included in the K horizontal programmable interconnect ways, each short horizontal interconnect line segment is connected to a long horizontal interconnect line segment of a k-th horizontal programmable interconnect way that is included in the K horizontal programmable interconnect ways through an inter-horizontal-channel programmable switch, and long horizontal interconnect line segments to which the inter-horizontal-channel programmable switches of arbitrary Mk contiguous tiles aligned in the horizontal direction are connected belong to different long horizontal lanes.
In accordance with a thirtieth aspect of the present invention, in the twenty-sixth aspect, in at least one horizontal programmable interconnect way that is not included in the K horizontal programmable interconnect ways, each short horizontal interconnect line segment is connected to a long horizontal interconnect line segment of a k-th horizontal programmable interconnect way that is included in the K horizontal programmable interconnect ways through an inter-horizontal-channel programmable switch, and long horizontal interconnect line segments to which the inter-horizontal-channel programmable switches of arbitrary Mk contiguous tiles aligned in the horizontal direction are connected belong to different long horizontal lanes.
In accordance with a thirty-first aspect of the present invention, in the twenty-ninth aspect, the natural numbers Mk and Pk are set to be relatively prime in at least one horizontal programmable interconnect way included in the K horizontal programmable interconnect ways.
In accordance with a thirty-second aspect of the present invention, in the thirtieth aspect, the natural numbers Mk and Pk are set to be relatively prime in at least one horizontal programmable interconnect way included in the K horizontal programmable interconnect ways.